from typing import List


class Trie:
    class _Node:
        def __init__(self):
            self.value = None
            self.weight = 0
            self.children = {}

        def __contains__(self, ch):
            return ch in self.children

        def __getitem__(self, ch):
            return self.children[ch]

        def __setitem__(self, ch, value):
            self.children[ch] = value

    def __init__(self):
        self.root = self._Node()

    def add(self, word, weight=1):
        """向字典树中添加词语"""
        node = self.root
        for ch in word:
            if ch not in node:
                node[ch] = self._Node()
            node.weight = max(node.weight, weight)
            node = node[ch]
        node.value = word
        node.weight = weight

    def __contains__(self, word):
        """判断词语是否存在"""
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return node.value == word

    def search(self, string):
        """寻找字符串中从头开始的第1个词语（如果没有找到则返回None）"""
        node = self.root
        for ch in string:
            if ch not in node:
                return "", -1
            node = node[ch]
            if node.value is not None:
                return node.value, node.weight
        return "", -1

    def start_with(self, string):
        """寻找字符串中是否有以string开头的"""
        node = self.root
        for ch in string:
            if ch not in node:
                return "", -1
            node = node[ch]
        return node.value, node.weight


class WordFilter:

    def __init__(self, words: List[str]):
        self.trie = Trie()
        for weight, word in enumerate(words):
            code = word + "#" + word
            for i in range(len(word) + 1):
                self.trie.add(code[i:], weight=weight)

    def f(self, prefix: str, suffix: str) -> int:
        code = suffix + "#" + prefix
        return self.trie.start_with(code)[1]


if __name__ == "__main__":
    obj = WordFilter(["apple"])
    print(obj.f("a", "e"))  # 0
    print(obj.f("b", ""))  # -1

    # 测试用例7/13 (节选)
    obj = WordFilter(
        ["cabaabaaaa", "ccbcababac", "bacaabccba", "bcbbcbacaa", "abcaccbcaa", "accabaccaa", "cabcbbbcca", "ababccabcb",
         "caccbbcbab", "bccbacbcba"])
    print(obj.f("bccbacbcba", "a"))  # 9
